package com.rui.study.algorithm.P_等差数列划分Ⅱ_子序列;

import java.util.HashMap;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-29 08:04
 **/
public class Solution2_动态规划_未解决 {
    /**
     * local[i][j] = Math.max(global[i][j-1] + Math.max(diff,0), local[i][j-1] + diff);
     * global[i][j] = Math.max(global[i][j-1], local[i][j]);
     * @param A
     * @return
     */
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        if (n < 3) {
            return 0;
        }
//        int[] state = new int[n];
        HashMap<Integer, Integer> state = new HashMap<>();

        int count = 0;
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                int diff = A[j] - A[i];
                Integer diffCount = state.get(diff);
                if (diffCount != null) {
                    count += ++diffCount;
                    state.put(diff, diffCount);
                } else {
                    state.put(diff, 1);
                }
            }
        }
        return count;
    }



    public static void main(String[] args) {
        int[] a = {1,3,5,7,9};

        long start = System.currentTimeMillis();
        Solution2_动态规划_未解决 solution = new Solution2_动态规划_未解决();
        int result = solution.numberOfArithmeticSlices(a);
        long end = System.currentTimeMillis();
        System.out.println("等差数列划分Ⅱ：" + result + ", 耗时[" + (end - start) + "ms]");
    }
}
